#include <iostream>
#include <fstream>
#include <omp.h>
using namespace std;

/* Ilość wierzcholkow. */
int N;
/* Ilość krawedzi. */
int M;

/* Dlugosci krawedzi. */
int **G;
/* Wartosci najkrotszycj sciezek. */
int **g;

/* 
 * Macierz kierowana ruchem. 
 * Prechowuje optymalne wartosci posrednich wierzcholkow.
 */
int **R;

/* 
 * Stała służąca za wartość nieskończoną. 
 * Z jakiegos powodu niedzala macro z <climits>
 */
const int INF = 10001;

void 	konstruktor	(void);
void	destruktor	(void);
void	wczytywanie	(fstream &plik);
void	setup		(void);
void	floyd		(void);
void	droga		(int u, int v);

 

int main() {
	fstream plik;
	plik.open("dane.txt");
	ios_base::sync_with_stdio(0);

	plik >> N >> M;
	konstruktor();

	setup();
	wczytywanie(plik);    
	plik.close();
	floyd();

	int a1,a2;
	cin >> a1 >> a2;
	cout << a1 << " -> " << a2 << " : " << g[a1-1][a2-1] << endl << a1 <<" ";
	droga(a1-1,a2-1);
	cout << a2 << endl;

	destruktor();
	return 0;
}

/* 
 * Funkcja dynamicznie tworzy tablice "G", "g" i "R".
 * Może niezbyt odkrywcze, ale C’est la vie...
 */
void konstruktor (void) {
	G = new int*[N];
	g = new int*[N];
	R = new int*[N];

	#pragma omp parallel for
	for(int i=0; i<N; ++i)
	{
		G[i] = new int[N];
		g[i] = new int[N];
		R[i] = new int[N];
	}
}

/* 
 * Funkcja dynamicznie usuwa tablice "G", "g" i "R".
 * Może niezbyt odkrywcze, ale C’est la vie...
 */
void destruktor (void) {
	#pragma omp parallel for
	for(int i=0; i<N; ++i)
	{
		delete [] R[i];
		delete [] g[i];
		delete [] G[i];
	}
	delete [] R;
	delete [] g;
	delete [] G;
}



/*
 * Funkcja wczytuje graf z pliku.
 * Przykladowe dane wejsciowe:
	5 10
	1 2 10
	1 5 5
	2 3 1
	2 5 2
	3 4 4
	4 3 6
	4 1 7
	5 2 3
	5 3 9
	5 4 2
 */
void wczytywanie(fstream &plik) {
	// Zmienne tymczasowe
	int u, v, w;
	#pragma omp for schedule(static)
	for(int i=0; i<M; ++i) 
	{
		plik >> u >> v >> w;
		G[u-1][v-1] = g[u-1][v-1] = w;
    }
}


/* 
 * Inicjalizuje tablice wartosciami poczatkowymi.
 */
void setup(void) {
	#pragma omp parallel for
	for(int i=0; i<N; ++i) 
	{
		for(int j=0; j<N; ++j) 
		{
			G[i][j] = INF;
			g[i][j] = INF;
			R[i][j] = -1;
		}
		G[i][i] = 0;
		g[i][i] = 0;
	}
}


/*
 * Znajdowanie najkrotszej sciezki pomiedzy kazda para wierzcholkow
 * w grafie i uzupelnia macierz kierowania ruchem, aby mozna bylo
 * odtworzyc przebieg kazdej drogi
 */
void floyd(void) {
	#pragma omp parallel for
	for(int k=0; k<N; ++k)
		for(int i=0; i<N; ++i)
			for(int j=0; j<N; ++j)
				if( g[i][j] > g[i][k] + g[k][j] )
				{ 
					g[i][j] = g[i][k] + g[k][j];
					// idac po sciezce i~>j trzeba przejsc przez k
					R[i][j]=k;						
                }
}


/*
 * Odtwarza najkrotsza sciezke pomiedzy danymi wierzcholkami wykorzystujac macierz kierowania ruchem
 */
void droga(int u, int v) {
	if( R[u][v] != -1 ) 
	{
		droga(u, R[u][v]);
		cout << R[u][v] + 1 <<" ";
		droga(R[u][v], v);
	}
}


